#pragma once

#define MAX_ELEMENT 1000

#include <fstream>
#include "Node.h"
using namespace std;

template<class T>
class Heap
{
public:
	Heap();
	~Heap();

	void pushElement(T* node);
	T* getTop();
	void adjustElement(int inx, T* node);
	void write(VNode *node, int type);

	inline T** getData() { return this->data; }
	inline int getSize() { return this->size; }
	inline bool isEmpty() { return this->size == 0; }

private:
	int size;
	T* data[MAX_ELEMENT];
};

template<typename T>
Heap<T>::Heap()
{
	this->size = 0;
	ofstream file("test.txt");
	file.close();
}

template<typename T>
Heap<T>::~Heap()
{
}

template<typename T>
void Heap<T>::write(VNode* node, int type)
{
	ofstream file;
	file.open("test.txt", ios::app);
	if (file.is_open())
	{
		if (type == 0)
		{
			file << "push element: ";
		}
		else
		{
			file << "pop element: ";
		}
		file << "(" << node->getX() << "," << node->getY() << ")";
		file << "   " << node->getG() << " + " << node->getH() << " = " << node->getF() << endl;
		for (int i = 0; i < size; i++)
		{
			node = data[i];
			file << "(" << node->getX() << "," << node->getY() << ")";
			file << "   " << node->getG() << " + " << node->getH() << " = " << node->getF() << endl;
		}
		file << endl;
		file.close();
	}
}

template<typename T>
void Heap<T>::pushElement(T* node)
{
	this->data[this->size++] = node;

	int i, j;
	T* temp;
	i = size - 1;
	while (i > 0)
	{
		j = (i - 1) / 2;
		if (*data[i] < *data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			i = j;
		}
		else
		{
			break;
		}
	}
	this->write(node, 0);
}

template<typename T>
T* Heap<T>::getTop()
{
	if (size <= 0)
	{
		return NULL;
	}

	T* top = data[0];
	data[0] = data[--size];

	int j;
	bool swap;
	T* temp;
	for (int i = 0; i <= (size - 2) / 2; i++)
	{
		swap = false;
		j = i * 2 + 1;
		if (*data[i] > *data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			swap = true;
		}
		j = i * 2 + 2;
		if (j > size - 1) break;
		if (*data[i] > *data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			swap = true;
		}
		if (!swap)
		{
			break;
		}
	}
	this->write(top, 1);

	return top;
}

template<class T>
inline void Heap<T>::adjustElement(int i, T * node)
{
	if (data[i] != node)
	{
		return;
	}

	T *temp;
	int j;
	while (i > 0)
	{
		j = (i - 1) / 2;
		if (*data[i] < *data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			i = j;
		}
		else
		{
			break;
		}
	}
}
